#include<string.h>
#define ASCIIL 256
#define F(x) ((x-1)>>1)
#define L(x) ((x<<1)+1)
#define R(x) ((x<<1)+2)
#define SWAP(a,b,tmp) {tmp=a;a=b;b=tmp;}

using namespace std;

//实现二叉堆模板类，小顶堆
template <class HeapType>
class CHeap
{
	HeapType* data, tmp;
	int size;

	void HeapUp(int ix)
	{//自底向顶维护堆
		int f;
		for (f = F(ix); ix && data[ix] < data[f]; ix = f, f = F(f))
			SWAP(data[ix], data[f], tmp);
	}

	void HeapDown(int ix)
	{//自顶向底维护堆
		int l, r, t;
		HeapType min, tmp;
		if (ix >= size) return;
		l = L(ix), r = R(ix);

		min = data[ix], t = ix;

		if (l < size && data[l] < min)
			t = l, min = data[l];
		if (r < size && data[r] < min)
			t = r, min = data[l];

		SWAP(data[ix], data[t], tmp);
		if (ix != t) HeapDown(t);
	}

public:
	CHeap()
	{//这里特殊应用，堆内元素个数不超过256
		size = 0;
		data = new HeapType[256];
	}
	~CHeap()
	{//释放内存
		delete[] data;
	}
	int getsize()
	{//返回堆大小
		return size;
	}
	void clear()
	{//清空堆
		size = 0;
	}
	void insert(HeapType e)
	{//向堆尾中插入元素，并向顶维护堆
		data[size++] = e;
		HeapUp(size - 1);
	}
	HeapType top()
	{//从堆顶取出元素，并向底维护堆
		HeapType ret = data[0];
		data[0] = data[--size];
		HeapDown(0); return ret;
	}
};

//哈夫曼树结点结构体实现
typedef struct talNode {

	unsigned char c;	//叶结点时对应ASCII值
	int weight;			//该结点权值
	int lt, rt;			//左、右结点下标

	talNode() {}

	talNode(unsigned char _c, int _p) :
		c(_c), weight(_p), lt(-1), rt(-1)
	{}

	talNode(unsigned char _c, int _p, int l, int r)
		:c(_c), weight(_p), lt(l), rt(r)
	{}

	bool operator < (talNode a)
	{//重载运算符“<”用于二叉堆内的比较
		return weight < a.weight;
	}

}HuffNode;


class CHuffMan {
	HuffNode arr[512];		//哈夫曼树结点数组
	int size;				//哈夫曼树结点个数
	bool code[256][64];		//ASCII对应编码方案
	int lenth[256];			//ASCII对应编码长度

	//lastcodelenth,ps[256],用于存储压缩文件中作为文件头
	int lastcodelenth;		//文件最后一个字符实用几位
	int ps[256];			//ASCII对应出现频率
	int soucelen, targetlen; //源及目标文件长度


	//私有成员函数，用于实现内部功能
	void SetHuffTree(int[]);			//根据字符频率生成哈夫曼树
	void SetHuffCode(int, bool[], int);//根据哈夫曼树生成编码方案
	void CreateHuff(int[]);			//创建哈夫曼树及编码方案
	void EnCodePre(char[]);			//压缩前预处理
	void DeCodePre(FILE*);				//解压前预处理
	void SaveHuffHead(FILE*);			//保存压缩文件头
	void ReadHuffHead(FILE*);			//读取压缩文件头

public:
	CHuffMan() { Clear(); }				//构造函数
	~CHuffMan() {}						//析构函数

	//公有成员函数，用于提供使用接口
	void Clear();						//清空当前对象内容
	void EnCodeFile(char[], char[]);	//编码，用于压缩文件，第一个参数为
										//源文件名，第二个参数为目标文件名
	void DeCodeFile(char[], char[]);	//解码，用于解压文件，第一个参数为
										//源文件名，第二个参数为目标文件名
	void GetHuffCode();					//输出ASCII对应编码方案
	int GetSouceLen();					//输出当前工作项的源文件长度
	int GetTargetLen();					//输出当前工作项的目标文件长度

};


void CHuffMan::SetHuffTree(int ps[])
{										//每次取出两权值最小的结点合并成新树，
										//加入堆，直至堆中只余有一个元素

	CHeap<HuffNode> hp;					//二叉堆对象

	for (int i = 0; i < ASCIIL; i++) {			//如果字符i出现过，则插入二插堆
		if (ps[i])
			hp.insert(HuffNode(i, ps[i]));
	}
	size = 0;								//初始化哈夫曼树中结点个数
	while (hp.getsize() > 1) {
		arr[size++] = hp.top();			//取出权值最小的两个结点
		arr[size++] = hp.top();
		hp.insert(HuffNode(0,
			arr[size - 1].weight + arr[size - 2].weight,
			size - 1, size - 2));			//合并结点，并插入堆
	}
	arr[size++] = hp.top();				//arr[size-1]为哈夫曼树根
}

void CHuffMan::SetHuffCode(int ix, bool stk[], int top)
{										//递归深搜哈夫曼树，生成所有存在的ASCII
										//的前缀码
	if (arr[ix].c) {						//如果
		if (top) {						//此判断用于只含有一类字符的文件
			memmove(code[arr[ix].c], stk, sizeof(bool) * top);
			lenth[arr[ix].c] = top;
		}
		else lenth[arr[ix].c] = 1;
		return;
	}
	stk[top] = 0;							//左子树的边设为0
	SetHuffCode(arr[ix].lt, stk, top + 1);	//递归进入左子树
	stk[top] = 1;							//右子树的边设为1
	SetHuffCode(arr[ix].rt, stk, top + 1);	//递归进入右子树
}

void CHuffMan::CreateHuff(int ps[])
{										//构造哈夫曼树及前缀码
	bool stk[64];
	SetHuffTree(ps);					//根据字符频率构造哈夫曼树
	SetHuffCode(size - 1, stk, 0);			//根据哈夫曼树生成前缀码
}
void CHuffMan::EnCodePre(char sfilename[])
{										//压缩文件预处理，读取字符出现频率
	FILE* fp;							//及构造哈夫曼树及前缀码
	int c;
	fp = fopen(sfilename, "rb");
	if (fp == NULL) {
		cout << "读取文件错误" << endl;
		exit(0);
	}
	memset(ps, 0, sizeof(ps));			//读取字符出现频率
	while (true) {
		c = fgetc(fp);
		if (feof(fp))break;
		ps[c]++;
	}
	fclose(fp);
	CreateHuff(ps);						//构造哈夫曼树及前缀码
}

void CHuffMan::DeCodePre(FILE* fp)
{										//解压文件预处理，读取压缩文件头
										//根据读取头信息构千哈夫曼树及前缀码
	ReadHuffHead(fp);
	CreateHuff(ps);
}

void CHuffMan::SaveHuffHead(FILE* fp)
{											//向压缩文件中写文件头
	fwrite((void*)&lastcodelenth, 4, 257, fp);//从lastcodelenth的地址开始的连续
											//4*257个字节，即lastcodelenth和
											//ps[256]数组内容
	targetlen += 4 * 257;
}

void CHuffMan::ReadHuffHead(FILE* fp)
{										//从缩文件中读文件头
	fread((void*)&lastcodelenth, 4, 257, fp);	//从lastcodelenth的地址开始的连续
											//4*257个字节，即lastcodelenth和
	soucelen += 4 * 257;						//ps[256]数组内容
}

void CHuffMan::Clear()
{											//清空前前工作项
	size = 0; soucelen = targetlen = 0;
	lastcodelenth = 0;
	memset(lenth, 0, sizeof(lenth));
	memset(ps, 0, sizeof(ps));
}

int CHuffMan::GetSouceLen()
{											//获取当前工作项的源文件长度
	return soucelen;
}

int CHuffMan::GetTargetLen()
{											//获取当前工作项的目标文件长度
	return targetlen;
}

void CHuffMan::GetHuffCode()
{											//输出当前工作项的编码前缀码方案
	int i;
	for (i = 0; i < ASCIIL; i++) {
		if (lenth[i] > 0) {						//如果前缀码不空
			printf("%c : ", i);				//输出ASCII码
			for (int j = 0; j < lenth[i]; j++) {
				printf("%d", code[i][j]);	//输出对应前缀码
			}
			puts("");
		}
	}
}

void CHuffMan::EnCodeFile(char sfilename[], char gfilename[])
{
	FILE* fp, * fpt;
	int c, data, l, i;

	EnCodePre(sfilename);					//压缩预处理，生成哈曼树及
											//字符前缀码

	fp = fopen(sfilename, "rb");
	fpt = fopen(gfilename, "wb");

	SaveHuffHead(fpt);						//写入压缩文件的头信息
											//!!!注意，此时lastcodelenth
											//为空，需压缩结束时重置
	l = data = 0;
	puts("Encoding ... ");
	//编码压缩过程，依次对源文件字符进行编码
	while (true) {							//存入一个字符中，用移位操作实现，每8位前
		c = fgetc(fp);						//缀码对应一个字符，将该字符存入目标文件，
		if (feof(fp)) break;					//最终不足8位的记录最后一位占用的前缀码长度
		soucelen++;							//源文件长度增加
		for (i = 0; i < lenth[c]; i++) {			//对data进行左移，空出最低位
			data <<= 1;						//对当前字符的前缀码当前们存储于data中
			data += code[c][i];
			if (++l % 8 == 0) {					//满8位，则存储
				fputc(data, fpt);
				targetlen++;				//目标文件长度增加
			}
		}
	}										//对最后的一个字符进行处理
	lastcodelenth = l % 8;						//记录实际占用位的长度
	data <<= 8 - lastcodelenth;					//空出剩余位
	fputc(data, fpt);						//输出至文件
	targetlen++;							//目标文件长度增加

	fseek(fpt, 0, SEEK_SET);					//!!!回溯至文件头，更新lastcodelenth至
	fwrite(&lastcodelenth, 4, 1, fpt);			//真实值

	fclose(fp);								//关闭文件
	fclose(fpt);
}

void CHuffMan::DeCodeFile(char sfilename[], char gfilename[])
{											//解压文件sfile至gfile
	FILE* fp = fopen(sfilename, "rb");
	FILE* fpt = fopen(gfilename, "wb");
	int c, t, l, i;							//l用于记录当前前缀码段的长度
	HuffNode cur;
	bool tmp[64];							//tmp[]用于记录当前的前缀码段

	DeCodePre(fp);
	l = 0;
	puts("Decoding ... ");

	fscanf(fp, "%c", &c);						//解码过程，压缩过程的逆过程，取出编码了的字符，
											//按位取出，存于tmp[]中，找出前缀码对应的字符
	while (!feof(fp)) {
		soucelen++;
		fscanf(fp, "%c", &t);
		if (feof(fp))break;

		for (i = l + 7; i >= l; i--) {				//按位取出前缀码
			tmp[i] = c & 1; c >>= 1;
		}l += 8;

		while (l >= 32) {						//如果当前前缀码段超出一定的长度，则取出前缀码
											//进行解码
			for (i = 0, cur = arr[size - 1]; !cur.c; i++)
				cur = tmp[i] ? arr[cur.rt] : arr[cur.lt];//找到前缀码段对应第一个字符
			fprintf(fpt, "%c", cur.c);				//输出至目标文件
			l -= i; targetlen++;						//前缀码段减去当前字符前缀码长度
			memmove(tmp, tmp + i, sizeof(bool) * l);		//数组顺移至开头，即从0开始记录当前的
													//前缀码段
		}c = t;
	}
	for (i = l + 7; i >= l; i--) {							//对最后一个字符做特殊处理
		tmp[i] = c & 1;									//取出每一位
		c >>= 1;
	}
	l += lastcodelenth;								//只利用最后一个字符的前lastcodelenth位
	while (l) {										//输出剩余的前缀码段对应的字符
		for (i = 0, cur = arr[size - 1]; !cur.c; i++)
			cur = tmp[i] ? arr[cur.rt] : arr[cur.lt];
		fprintf(fpt, "%c", cur.c); l -= i; targetlen++;
		memmove(tmp, tmp + i, sizeof(bool) * l);
	}
	fclose(fp); fclose(fpt);							//关闭文件

}

bool Menu(int& op)
{
	system("cls");
	printf("|\t哈夫曼编码实现文件压缩\t|\n");
	printf("功能:\n");
	printf("_________________________________\n");
	printf("|\t1、\t压缩文件\t|\n");
	printf("|\t2、\t解压文件\t|\n");
	printf("|\t3、\t输出编码方案\t|\n");
	printf("|\t0、\t退出     \t|\n");
	printf("---------------------------------\n");
	do {
		printf("请选择：");
		scanf("%d", &op);
	} while (op < 0 || op>3);
	return op ? true : false;
}

void huf_Compress()
{
	int op;
	char file1[32], file2[32];
	CHuffMan work;
	char step[2];
	while (Menu(op)) {
		switch (op) {
		case 1:
			printf("请输入待压缩文件名(.txt)：");
			scanf("%s", file1);
			printf("请输入压缩文件名(.huf)：");
			scanf("%s", file2);
			work.Clear();
			work.EnCodeFile(file1, file2);
			printf("源文件长度：/t%d/n", work.GetSouceLen());
			printf("目标文件长度:/t%d/n", work.GetTargetLen());
			break;
		case 2:
			printf("请输入待压缩文件名(.huf)：");
			scanf("%s", file1);
			printf("请输入压缩文件名(.txt)：");
			scanf("%s", file2);
			work.Clear();
			work.DeCodeFile(file1, file2);
			printf("源文件长度：/t%d/n", work.GetSouceLen());
			printf("目标文件长度:/t%d/n", work.GetTargetLen());
			break;
		case 3:
			work.GetHuffCode();
			break;
		}
		puts("按任意键继续...");
		gets(step);
		gets(step);
	}
	return ;
}
